Algorithmic Puzzles by Anany Levitin & Maria Levitin

Algorithmic Puzzles by Anany Levitin & Maria Levitin

Author:Anany Levitin & Maria Levitin [Levitin, Anany]
Language: eng
Format: epub
Publisher: Oxford University Press
Published: 2011-09-16T00:00:00+00:00


Comments R(n) differs slightly from the canonical Fibonacci sequence, which is usually defined by the same recurrence equation F(n) = F(n − 1) + F(n − 2) but with different initial conditions, namely, F(0) = 0 and F(1) = 1. Obviously, R(n) = F(n + 1) for n ≥ 0. Also note that we could find R12 by using one of the two well-known formulas for the Fibonacci numbers (e.g., [Gra94, Section 6.6]):

and

rounded to the nearest integer.

From the algorithmic perspective, the puzzle specifies an algorithm and asks to determine its output. This is a relatively rare type of algorithmic puzzle; for most of them, the object is to design an algorithm rather than to determine the output of an algorithm given.

The puzzle appeared in The Book of Calculation(Liber Abaci), written by the Italian mathematician Leonardo of Piza, also known as Fibonacci, in 1202. (The other and more important contribution of the book was the promotion of the Hindu-Arabic numeral system in Europe.) The sequence that solves the problem is one of the most interesting and important sequences ever discovered. Not only does it have many fascinating properties, but it arises, often quite unexpectedly, in many areas of nature and science. Nowadays there exist a large number of books and websites, as well as a special journal called Fibonacci Quarterly, devoted to the Fibonacci sequence and its applications. In particular, the website by the British mathematician Ron Knott [Knott] contains a score of puzzles related to the Fibonacci numbers.



Download



Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.